package com.cg.offer;

import org.junit.Test;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 剑指Offer 39.数组中出现次数超过一半的数字
 *
 * @program: LeetCode->Offer_39
 * @description: 剑指Offer 39.数组中出现次数超过一半的数字
 * @author: cg
 * @create: 2022-03-31 20:54
 **/
public class Offer_39 {

    @Test
    public void test39() {
        System.out.println(majorityElement(new int[]{1, 2, 3, 2, 2, 2, 5, 4, 2}));
    }

    /**
     * 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
     * <p>
     * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
     * <p>
     * 示例 1:
     * 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
     * 输出: 2
     * <p>
     * 限制：
     * 1 <= 数组长度 <= 50000
     *
     * @param nums
     * @return
     */
    public int majorityElement(int[] nums) {
        /*// 数组排序法
        Arrays.sort(nums);
        return nums[(nums.length) / 2];*/
        // 摩尔投票法
        int x = 0, votes = 0;
        for (int num : nums) {
            if (votes == 0) {
                x = num;
            }
            if (x == num) {
                votes += 1;
            } else {
                votes += -1;
            }
        }
        return x;
    }

}
